package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/7/6.<br><br>
 *
 * 简单：最大子数组和
 */
public class Topic53 {
    public static void main(String[] args) {
        BaseSolution solution = new Solution3();

        int[] array = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(solution.maxSubArray(array));

        array = new int[] {1};
        System.out.println(solution.maxSubArray(array));

        array = new int[] {5,4,-1,7,8};
        System.out.println(solution.maxSubArray(array));

        array = new int[] {-1};
        System.out.println(solution.maxSubArray(array));
    }

    private interface BaseSolution {
        int maxSubArray(int[] nums);
    }

    private static class Solution1 implements BaseSolution {

        @Override
        public int maxSubArray(int[] nums) {
            if(nums == null || nums.length == 0) {
                return 0;
            }

            int maxSum = Integer.MIN_VALUE;
            for(int i = 0; i < nums.length; i++) {
                int sum = 0;

                for(int j = i; j < nums.length; j++) {
                    sum += nums[j];
                    maxSum = Math.max(maxSum, sum);
                }
            }

            return maxSum;
        }
    }

    private static class Solution2 implements BaseSolution {

        @Override
        public int maxSubArray(int[] nums) {
            if(nums == null || nums.length == 0) {
                return 0;
            }

            int maxSum = Integer.MIN_VALUE;
            int sum = 0;
            for(int value : nums) {
                if(sum < 0) {
                    sum = 0;
                }

                sum += value;
                maxSum = Math.max(sum, maxSum);
            }

            return maxSum;
        }
    }

    private static class Solution3 implements BaseSolution {

        @Override
        public int maxSubArray(int[] nums) {
            int temp = 0;
            int result = nums[0];
            for(int value : nums) {
                temp = Math.max(temp + value, value);
                result = Math.max(result, temp);
            }
            return result;
        }
    }
}
